/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.

	Large portions of this file are based on Quake 3's tr_curve.c and tr_bsp.c,
	both Copyright (C) 1999-2005 Id Software, Inc.
******************************************************************************/

using System;
using System.Collections.Generic;
using System.Text;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Graphics.PackedVector;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;

namespace Cobalt.Content.Pipeline.Quake.Bsp
{
	using DrawVert = BspImporter.DrawVert;

	internal class Patch
	{
		private Vector3 lodOrigin;
		private float lodRadius;
		private int lodFixed;
		private bool lodStitched;

		private int width;
		private int height;
		private List<float> widthLodError = new List<float>();
		private List<float> heightLodError = new List<float>();
		private List<DrawVert> verts = new List<DrawVert>();

		private GeometryContent targetMesh;
		public GeometryContent TargetMesh { get { return targetMesh; } set { targetMesh = value; } }

		private static float VectorNormalize( ref Vector3 v )
		{
			float len = v.Length();

			if( len != 0 )
			{
				float iLen = 1.0F / len;

				v.X *= iLen;
				v.Y *= iLen;
				v.Z *= iLen;
			}

			return len;
		}

		private static float VectorNormalize2( Vector3 v, out Vector3 o )
		{
			float len = v.Length();

			if( len != 0 )
			{
				float ilen = 1.0F / len;
				o.X = v.X * ilen;
				o.Y = v.Y * ilen;
				o.Z = v.Z * ilen;
			}
			else
			{
				o = new Vector3();
			}

			return len;
		}

		private static DrawVert LerpDrawVert( DrawVert a, DrawVert b )
		{
			DrawVert ret = new DrawVert();

			ret.Position = (a.Position + b.Position) * 0.5F;
			ret.TextureCoord = (a.TextureCoord + b.TextureCoord) * 0.5F;
			ret.LightmapCoord = (a.LightmapCoord + b.LightmapCoord) * 0.5F;
			ret.Color = new Color(
				(byte)((a.Color.R + b.Color.R) / 2),
				(byte)((a.Color.G + b.Color.G) / 2),
				(byte)((a.Color.B + b.Color.B) / 2),
				(byte)((a.Color.A + b.Color.A) / 2) );

			return ret;
		}

		private static void Transpose( int width, int height, DrawVert[][] ctrl )
		{
			if( width > height )
			{
				for( int i = 0; i < height; i++ )
				{
					for( int j = i + 1; j < width; j++ )
					{
						if( j < height )
						{
							// swap the value
							DrawVert temp = ctrl[j][i];
							ctrl[j][i] = ctrl[i][j];
							ctrl[i][j] = temp;
						}
						else
						{
							// just copy
							ctrl[j][i] = ctrl[i][j];
						}
					}
				}
			}
			else
			{
				for( int i = 0; i < width; i++ )
				{
					for( int j = i + 1; j < height; j++ )
					{
						if( j < width )
						{
							// swap the value
							DrawVert temp = ctrl[i][j];
							ctrl[i][j] = ctrl[j][i];
							ctrl[j][i] = temp;
						}
						else
						{
							// just copy
							ctrl[i][j] = ctrl[j][i];
						}
					}
				}
			}
		}

		private static readonly int[][] neighbors = new int[][]
		{
			new int[] {0, 1},
			new int[] {1, 1},
			new int[] {1, 0},
			new int[] {1, -1},
			new int[] {0, -1},
			new int[] {-1, -1},
			new int[] {-1, 0},
			new int[] {-1, 1}
		};

		private static void MakeMeshNormals( int width, int height, DrawVert[][] ctrl )
		{
			//handles all the complicated wrapping and degenerate cases
			int i, j, k, dist;
			Vector3 normal;
			Vector3 sum;
			int count = 0;
			Vector3 basev;
			Vector3 delta;
			int x, y;
			Vector3 temp;
			Vector3[] around = new Vector3[8];
			bool[] good = new bool[8];
			bool wrapHeight;
			float len;

			bool wrapWidth = false;
			for( i = 0; i < height; i++ )
			{
				delta = ctrl[i][0].Position - ctrl[i][width - 1].Position;
				len = delta.LengthSquared();
				if( len > 1.0 )
				{
					break;
				}
			}
			if( i == height )
			{
				wrapWidth = true;
			}

			wrapHeight = false;
			for( i = 0; i < width; i++ )
			{
				delta = ctrl[0][i].Position - ctrl[height - 1][i].Position;
				len = delta.LengthSquared();
				if( len > 1.0 )
				{
					break;
				}
			}
			if( i == width )
			{
				wrapHeight = true;
			}


			for( i = 0; i < width; i++ )
			{
				for( j = 0; j < height; j++ )
				{
					count = 0;
					basev = ctrl[j][i].Position;
					for( k = 0; k < 8; k++ )
					{
						around[k] = new Vector3();
						good[k] = false;

						for( dist = 1; dist <= 3; dist++ )
						{
							x = i + neighbors[k][0] * dist;
							y = j + neighbors[k][1] * dist;
							if( wrapWidth )
							{
								if( x < 0 )
								{
									x = width - 1 + x;
								}
								else if( x >= width )
								{
									x = 1 + x - width;
								}
							}
							if( wrapHeight )
							{
								if( y < 0 )
								{
									y = height - 1 + y;
								}
								else if( y >= height )
								{
									y = 1 + y - height;
								}
							}

							if( x < 0 || x >= width || y < 0 || y >= height )
							{
								break;					// edge of patch
							}
							temp = ctrl[y][x].Position - basev;
							if( VectorNormalize2( temp, out temp ) == 0 )
							{
								continue;				// degenerate edge, get more dist
							}
							else
							{
								good[k] = true;
								around[k] = temp;
								break;					// good edge
							}
						}
					}

					sum = new Vector3();
					for( k = 0; k < 8; k++ )
					{
						if( !good[k] || !good[(k + 1) & 7] )
						{
							continue;	// didn't get two points
						}
						normal = Vector3.Cross( around[(k + 1) & 7], around[k] );
						if( VectorNormalize2( normal, out normal ) == 0 )
						{
							continue;
						}
						sum += normal;
						count++;
					}
					if( count == 0 )
					{
						//bad normal
						count = 1;
					}
					ctrl[j][i].Normal = Vector3.Normalize( sum );
				}
			}
		}

		private static void PutPointsOnCurve( int width, int height, DrawVert[][] ctrl )
		{
			int i, j;
			DrawVert prev, next;

			for( i = 0; i < width; i++ )
			{
				for( j = 1; j < height; j += 2 )
				{
					prev = LerpDrawVert( ctrl[j][i], ctrl[j + 1][i] );
					next = LerpDrawVert( ctrl[j][i], ctrl[j - 1][i] );
					ctrl[j][i] = LerpDrawVert( prev, next );
				}
			}


			for( j = 0; j < height; j++ )
			{
				for( i = 1; i < width; i += 2 )
				{
					prev = LerpDrawVert( ctrl[j][i], ctrl[j][i + 1] );
					next = LerpDrawVert( ctrl[j][i], ctrl[j][i - 1] );
					ctrl[j][i] = LerpDrawVert( prev, next );
				}
			}
		}

		private Patch( int width, int height, DrawVert[][] ctrl,
			float[][] errorTable )
		{
			widthLodError.AddRange( errorTable[0] );
			heightLodError.AddRange( errorTable[1] );

			this.width = width;
			this.height = height;

			Vector3 boundMin = new Vector3( 99999 );
			Vector3 boundMax = new Vector3( -99999 );

			verts.Capacity = width * height;

			for( int y = 0; y < height; y++ )
			{
				for( int x = 0; x < width; x++ )
				{
					verts.Add( ctrl[y][x] );

					boundMin = Vector3.Min( boundMin, ctrl[y][x].Position );
					boundMax = Vector3.Max( boundMax, ctrl[y][x].Position );
				}
			}

			// compute local origin and bounds
			lodOrigin = (boundMin + boundMax) * 0.5F;
			lodRadius = (boundMin - lodOrigin).Length();

			lodFixed = 0;
			lodStitched = false;
		}

		private static DrawVert[][] MakeGridArray( int width, int height )
		{
			DrawVert[][] ret = new DrawVert[height][];
			for( int i = 0; i < ret.Length; i++ )
				ret[i] = new DrawVert[width];
			return ret;
		}

		private const int MAX_GRID_SIZE = 65;
		private const int MAX_PATCH_SIZE = 32;

		public static Patch SubdividePatchToGrid( int width, int height, DrawVert[] points )
		{
			int i, j, k;

			DrawVert prev = new DrawVert();
			DrawVert next = new DrawVert();
			DrawVert mid = new DrawVert();

			float len, maxLen;

			int dir;
			int t;

			DrawVert[][] ctrl = Helpers.CreateSquareArray<DrawVert>( MAX_GRID_SIZE, MAX_GRID_SIZE );
			float[][] errorTable = Helpers.CreateSquareArray<float>( 2, MAX_GRID_SIZE );

			for( i = 0; i < width; i++ )
			{
				for( j = 0; j < height; j++ )
				{
					ctrl[j][i] = points[j * width + i];
				}
			}

			for( dir = 0; dir < 2; dir++ )
			{

				// horizontal subdivisions
				for( j = 0; j + 2 < width; j += 2 )
				{
					// check subdivided midpoints against control points

					// FIXME: also check midpoints of adjacent patches against the control points
					// this would basically stitch all patches in the same LOD group together.

					maxLen = 0;
					for( i = 0; i < height; i++ )
					{
						Vector3 midxyz;
						Vector3 midxyz2;
						Vector3 vdir;
						Vector3 projected;
						float d;

						// calculate the point on the curve
						midxyz = (ctrl[i][j].Position + ctrl[i][j + 1].Position * 2 + ctrl[i][j + 2].Position) * 0.25F;

						// see how far off the line it is
						// using dist-from-line will not account for internal
						// texture warping, but it gives a lot less polygons than
						// dist-from-midpoint
						midxyz -= ctrl[i][j].Position;
						vdir = Vector3.Normalize( ctrl[i][j + 2].Position - ctrl[i][j].Position );

						d = Vector3.Dot( midxyz, vdir );
						projected = vdir * d;
						midxyz2 = midxyz - projected;
						len = midxyz2.LengthSquared(); // we will do the sqrt later
						if( len > maxLen )
							maxLen = len;
					}

					maxLen = (float)Math.Sqrt( maxLen );

					// if all the points are on the lines, remove the entire columns
					if( maxLen < 0.1f )
					{
						errorTable[dir][j + 1] = 999;
						continue;
					}

					// see if we want to insert subdivided columns
					if( width + 2 > MAX_GRID_SIZE )
					{
						errorTable[dir][j + 1] = 1.0f / maxLen;
						continue;	// can't subdivide any more
					}

					if( maxLen <= 4 ) //4 = high quality value of r_subdivisions
					{
						errorTable[dir][j + 1] = 1.0f / maxLen;
						continue;	// didn't need subdivision
					}

					errorTable[dir][j + 2] = 1.0f / maxLen;

					// insert two columns and replace the peak
					width += 2;
					for( i = 0; i < height; i++ )
					{
						prev = LerpDrawVert( ctrl[i][j], ctrl[i][j + 1] );
						next = LerpDrawVert( ctrl[i][j + 1], ctrl[i][j + 2] );
						mid = LerpDrawVert( prev, next );

						for( k = width - 1; k > j + 3; k-- )
						{
							ctrl[i][k] = ctrl[i][k - 2];
						}

						ctrl[i][j + 1] = prev;
						ctrl[i][j + 2] = mid;
						ctrl[i][j + 3] = next;
					}

					// back up and recheck this set again, it may need more subdivision
					j -= 2;

				}

				Transpose( width, height, ctrl );
				t = width;
				width = height;
				height = t;
			}


			// put all the aproximating points on the curve
			PutPointsOnCurve( width, height, ctrl );

			// cull out any rows or columns that are colinear
			for( i = 1; i < width - 1; i++ )
			{
				if( errorTable[0][i] != 999 )
				{
					continue;
				}
				for( j = i + 1; j < width; j++ )
				{
					for( k = 0; k < height; k++ )
					{
						ctrl[k][j - 1] = ctrl[k][j];
					}
					errorTable[0][j - 1] = errorTable[0][j];
				}
				width--;
			}

			for( i = 1; i < height - 1; i++ )
			{
				if( errorTable[1][i] != 999 )
				{
					continue;
				}
				for( j = i + 1; j < height; j++ )
				{
					for( k = 0; k < width; k++ )
					{
						ctrl[j - 1][k] = ctrl[j][k];
					}
					errorTable[1][j - 1] = errorTable[1][j];
				}
				height--;
			}

			// calculate normals
			MakeMeshNormals( width, height, ctrl );

			return new Patch( width, height, ctrl, errorTable );
		}

		private static Patch GridInsertColumn( Patch grid, int column, int row, Vector3 point, float loderror )
		{
			int i, j;
			int width, height, oldwidth;
			DrawVert[][] ctrl = Helpers.CreateSquareArray<DrawVert>( MAX_GRID_SIZE, MAX_GRID_SIZE );
			float[][] errorTable = Helpers.CreateSquareArray<float>( 2, MAX_GRID_SIZE );

			oldwidth = 0;
			width = grid.width + 1;

			if( width > MAX_GRID_SIZE )
				throw new Exception( "Can't grow patch." );

			height = grid.height;
			for( i = 0; i < width; i++ )
			{
				if( i == column )
				{
					//insert new column
					for( j = 0; j < grid.height; j++ )
					{
						ctrl[j][i] = LerpDrawVert( grid.verts[j * grid.width + i - 1], grid.verts[j * grid.width + i] );
						if( j == row )
							ctrl[j][i].Position = point;
					}

					errorTable[0][i] = loderror;
					continue;
				}

				errorTable[0][i] = grid.widthLodError[oldwidth];
				for( j = 0; j < grid.height; j++ )
					ctrl[j][i] = grid.verts[j * grid.width + oldwidth];

				oldwidth++;
			}

			for( j = 0; j < grid.height; j++ )
				errorTable[1][j] = grid.heightLodError[j];

			// put all the aproximating points on the curve
			//PutPointsOnCurve( ctrl, width, height );
			// calculate normals
			MakeMeshNormals( width, height, ctrl );

			//create a new grid
			Patch ret = new Patch( width, height, ctrl, errorTable );
			ret.lodRadius = grid.lodRadius;
			ret.lodOrigin = grid.lodOrigin;

			return ret;
		}

		private static Patch GridInsertRow( Patch grid, int row, int column, Vector3 point, float loderror )
		{
			int i, j;
			int width, height, oldheight;
			DrawVert[][] ctrl = Helpers.CreateSquareArray<DrawVert>( MAX_GRID_SIZE, MAX_GRID_SIZE );
			float[][] errorTable = Helpers.CreateSquareArray<float>( 2, MAX_GRID_SIZE );

			oldheight = 0;
			width = grid.width;
			height = grid.height + 1;

			if( height > MAX_GRID_SIZE )
				throw new Exception( "Can't grow patch." );

			for( i = 0; i < height; i++ )
			{
				if( i == row )
				{
					//insert new row
					for( j = 0; j < grid.width; j++ )
					{
						ctrl[i][j] = LerpDrawVert( grid.verts[(i - 1) * grid.width + j], grid.verts[i * grid.width + j] );
						if( j == column )
							ctrl[i][j].Position = point;
					}
					errorTable[1][i] = loderror;
					continue;
				}

				errorTable[1][i] = grid.heightLodError[oldheight];
				for( j = 0; j < grid.width; j++ )
					ctrl[i][j] = grid.verts[oldheight * grid.width + j];

				oldheight++;
			}

			for( j = 0; j < grid.width; j++ )
				errorTable[0][j] = grid.widthLodError[j];
			// put all the aproximating points on the curve
			//PutPointsOnCurve( ctrl, width, height );
			// calculate normals
			MakeMeshNormals( width, height, ctrl );

			//create a new grid
			Patch ret = new Patch( width, height, ctrl, errorTable );
			ret.lodRadius = grid.lodRadius;
			ret.lodOrigin = grid.lodOrigin;

			return ret;
		}

		private static bool MergedWidthPoints( Patch grid, int offset )
		{
			int i, j;

			for( i = 1; i < grid.width - 1; i++ )
			{
				for( j = i + 1; j < grid.width - 1; j++ )
				{
					if( !Helpers.Equals( grid.verts[i + offset].Position, grid.verts[j + offset].Position, 0.1F ) )
						continue;

					return true;
				}
			}

			return false;
		}

		private static bool MergedHeightPoints( Patch grid, int offset )
		{
			int i, j;

			for( i = 1; i < grid.height - 1; i++ )
			{
				for( j = i + 1; j < grid.height - 1; j++ )
				{
					if( !Helpers.Equals( grid.verts[grid.width * i + offset].Position, grid.verts[grid.width * j + offset].Position, 0.1F ) )
						continue;

					return true;
				}
			}

			return false;
		}

		private static void FixSharedVertexLodError( List<Patch> patches, int start, Patch grid1 )
		{
			/*
				NOTE:	never sync LoD through grid edges with merged points!

				FIXME:	write generalized version that also avoids
						cracks between a patch and one that meets half way?
			*/

			for( int j = start; j < patches.Count; j++ )
			{
				Patch grid2 = patches[j];
				if( grid2.lodFixed == 2 )
					//LOD errors are already fixed for this patch
					continue;

				if( grid1.lodRadius != grid2.lodRadius )
					// grids in the same LOD group should have the exact same lod radius
					continue;

				if( grid1.lodOrigin != grid2.lodOrigin )
					//grids in the same LOD group should have the exact same lod origin
					continue;

				bool touch = false;
				for( int n = 0; n < 2; n++ )
				{
					int offset1 = n != 0 ? (grid1.height - 1) * grid1.width : 0;

					if( MergedWidthPoints( grid1, offset1 ) )
						continue;

					for( int k = 1; k < grid1.width - 1; k++ )
					{
						for( int m = 0; m < 2; m++ )
						{
							int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;

							if( MergedWidthPoints( grid2, offset2 ) )
								continue;

							for( int l = 1; l < grid2.width - 1; l++ )
							{
								if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
									continue;

								// ok the points are equal and should have the same lod error
								grid2.widthLodError[l] = grid1.widthLodError[k];
								touch = true;
							}
						}

						for( int m = 0; m < 2; m++ )
						{
							int offset2 = m != 0 ? grid2.width - 1 : 0;

							if( MergedHeightPoints( grid2, offset2 ) )
								continue;

							for( int l = 1; l < grid2.height - 1; l++ )
							{
								if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
									continue;

								// ok the points are equal and should have the same lod error
								grid2.heightLodError[l] = grid1.widthLodError[k];
								touch = true;
							}
						}
					}
				}
				for( int n = 0; n < 2; n++ )
				{
					int offset1 = n != 0 ? grid1.width - 1 : 0;

					if( MergedHeightPoints( grid1, offset1 ) )
						continue;

					for( int k = 1; k < grid1.height - 1; k++ )
					{
						for( int m = 0; m < 2; m++ )
						{
							int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;

							if( MergedWidthPoints( grid2, offset2 ) )
								continue;

							for( int l = 1; l < grid2.width - 1; l++ )
							{
								if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
									continue;

								// ok the points are equal and should have the same lod error
								grid2.widthLodError[l] = grid1.heightLodError[k];
								touch = true;
							}
						}

						for( int m = 0; m < 2; m++ )
						{
							int offset2 = m != 0 ? grid2.width - 1 : 0;

							if( MergedHeightPoints( grid2, offset2 ) )
								continue;

							for( int l = 1; l < grid2.height - 1; l++ )
							{
								if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
									continue;

								// ok the points are equal and should have the same lod error
								grid2.heightLodError[l] = grid1.heightLodError[k];
								touch = true;
							}
						}
					}
				}

				if( touch )
				{
					grid2.lodFixed = 2;
					FixSharedVertexLodError( patches, start, grid2 );

					//NOTE: this would be correct but makes things really slow
					//grid2.lodFixed = 1;
				}
			}
		}

		public static void FixSharedVertexLodError( List<Patch> patches )
		{
			/*
				This function assumes that all patches in one group are nicely stitched together for the highest LoD.
				If this is not the case this function will still do its job but won't fix the highest LoD cracks.
			*/
			for( int i = 0; i < patches.Count; i++ )
			{
				Patch grid1 = patches[i];

				if( grid1.lodFixed != 0 )
					continue;

				grid1.lodFixed = 2;

				//recursively fix other patches in the same LOD group
				FixSharedVertexLodError( patches, i + 1, grid1 );
			}
		}

		private static bool StitchPatches( Patch grid1, Patch grid2 )
		{
			for( int n = 0; n < 2; n++ )
			{
				int offset1 = n != 0 ? (grid1.height - 1) * grid1.width : 0;

				if( MergedWidthPoints( grid1, offset1 ) )
					continue;

				for( int k = 0; k < grid1.width - 2; k += 2 )
				{
					for( int m = 0; m < 2; m++ )
					{
						if( grid2.width >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;
						for( int l = 0; l < grid2.width - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[k + 2 + offset1].Position, grid2.verts[l + 1 + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[l + offset2].Position, grid2.verts[l + 1 + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert column into grid2 right after after column l
							int row = m != 0 ? grid2.height - 1 : 0;

							grid2 = GridInsertColumn( grid2, l + 1, row, grid1.verts[k + 1 + offset1].Position, grid1.widthLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}

					for( int m = 0; m < 2; m++ )
					{
						if( grid2.height >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? grid2.width - 1 : 0;

						for( int l = 0; l < grid2.height - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[k + 2 + offset1].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[grid2.width * l + offset2].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert row into grid2 right after after row l
							int column = m != 0 ? grid2.width - 1 : 0;

							grid2 = GridInsertRow( grid2, l + 1, column, grid1.verts[k + 1 + offset1].Position, grid1.widthLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}
				}
			}

			for( int n = 0; n < 2; n++ )
			{
				int offset1 = n != 0 ? grid1.width - 1 : 0;

				if( MergedHeightPoints( grid1, offset1 ) )
					continue;

				for( int k = 0; k < grid1.height - 2; k += 2 )
				{
					for( int m = 0; m < 2; m++ )
					{
						if( grid2.width >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;

						for( int l = 0; l < grid2.width - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[grid1.width * (k + 2) + offset1].Position, grid2.verts[l + 1 + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[l + offset2].Position, grid2.verts[(l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert column into grid2 right after after column l
							int row = m != 0 ? grid2.height - 1 : 0;

							grid2 = GridInsertColumn( grid2, l + 1, row, grid1.verts[grid1.width * (k + 1) + offset1].Position,
								grid1.heightLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}

					for( int m = 0; m < 2; m++ )
					{

						if( grid2.height >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? grid2.width - 1 : 0;

						for( int l = 0; l < grid2.height - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[grid1.width * (k + 2) + offset1].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[grid2.width * l + offset2].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert row into grid2 right after after row l
							int column = m != 0 ? grid2.width - 1 : 0;
							grid2 = GridInsertRow( grid2, l + 1, column, grid1.verts[grid1.width * (k + 1) + offset1].Position, grid1.heightLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}
				}
			}

			for( int n = 0; n < 2; n++ )
			{
				int offset1 = n != 0 ? (grid1.height - 1) * grid1.width : 0;

				if( MergedWidthPoints( grid1, offset1 ) )
					continue;

				for( int k = grid1.width - 1; k > 1; k -= 2 )
				{
					for( int m = 0; m < 2; m++ )
					{
						if( grid2.width >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;

						for( int l = 0; l < grid2.width - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[k - 2 + offset1].Position, grid2.verts[l + 1 + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[l + offset2].Position, grid2.verts[(l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert column into grid2 right after after column l
							int row = m != 0 ? grid2.height - 1 : 0;
							grid2 = GridInsertColumn( grid2, l + 1, row, grid1.verts[k - 1 + offset1].Position, grid1.widthLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}

					for( int m = 0; m < 2; m++ )
					{
						if( grid2.height >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? grid2.width - 1 : 0;

						for( int l = 0; l < grid2.height - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[k - 2 + offset1].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[grid2.width * l + offset2].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert row into grid2 right after after row l
							int column = m != 0 ? grid2.width - 1 : 0;
							grid2 = GridInsertRow( grid2, l + 1, column, grid1.verts[k - 1 + offset1].Position, grid1.widthLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}
				}
			}

			for( int n = 0; n < 2; n++ )
			{
				int offset1 = n != 0 ? grid1.width - 1 : 0;

				if( MergedHeightPoints( grid1, offset1 ) )
					continue;

				for( int k = grid1.height - 1; k > 1; k -= 2 )
				{
					for( int m = 0; m < 2; m++ )
					{
						if( grid2.width >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? (grid2.height - 1) * grid2.width : 0;

						for( int l = 0; l < grid2.width - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[grid1.width * (k - 2) + offset1].Position, grid2.verts[l + 1 + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[l + offset2].Position, grid2.verts[(l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert column into grid2 right after after column l
							int row = m != 0 ? grid2.height - 1 : 0;
							grid2 = GridInsertColumn( grid2, l + 1, row, grid1.verts[grid1.width * (k - 1) + offset1].Position, grid1.heightLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}

					for( int m = 0; m < 2; m++ )
					{

						if( grid2.height >= MAX_GRID_SIZE )
							break;

						int offset2 = m != 0 ? grid2.width - 1 : 0;

						for( int l = 0; l < grid2.height - 1; l++ )
						{
							if( !Helpers.Equals( grid1.verts[grid1.width * k + offset1].Position, grid2.verts[grid2.width * l + offset2].Position, 0.1F ) )
								continue;

							if( !Helpers.Equals( grid1.verts[grid1.width * (k - 2) + offset1].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.1F ) )
								continue;

							if( Helpers.Equals( grid2.verts[grid2.width * l + offset2].Position, grid2.verts[grid2.width * (l + 1) + offset2].Position, 0.01F ) )
								continue;

							//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
							// insert row into grid2 right after after row l
							int column = m != 0 ? grid2.width - 1 : 0;
							grid2 = GridInsertRow( grid2, l + 1, column, grid1.verts[grid1.width * (k - 1) + offset1].Position, grid1.heightLodError[k + 1] );
							grid2.lodStitched = false;

							return true;
						}
					}
				}
			}

			return false;
		}

		private static int TryStitchingPatch( List<Patch> patches, int grid1num )
		{
			/*
				This function will try to stitch patches in the same LoD group together for the highest LoD.

				Only single missing vertice cracks will be fixed.

				Vertices will be joined at the patch side a crack is first found, at the other side
				of the patch (on the same row or column) the vertices will not be joined and cracks
				might still appear at that side.
			*/
			int numstitches = 0;

			Patch grid1 = patches[grid1num];

			for( int j = 0; j < patches.Count; j++ )
			{
				Patch grid2 = patches[j];

				if( grid1.lodRadius != grid2.lodRadius )
					// grids in the same LOD group should have the exact same lod radius
					continue;

				if( grid1.lodOrigin != grid2.lodOrigin )
					// grids in the same LOD group should have the exact same lod origin
					continue;

				while( StitchPatches( patches[grid1num], patches[j] ) )
					numstitches++;
			}

			return numstitches;
		}

		public static int StitchAllPatches( List<Patch> patches )
		{
			int numstitches = 0;

			bool stitched = true;
			while( stitched )
			{
				stitched = false;
				for( int i = 0; i < patches.Count; i++ )
				{
					Patch grid1 = patches[i];

					if( grid1.lodStitched )
						continue;

					grid1.lodStitched = true;
					stitched = true;

					numstitches += TryStitchingPatch( patches, i );
				}
			}

			return numstitches;
		}

		public void GenerateGeometry()
		{
			int numVerts = width * height;
			int numQuads = (width - 1) * (height - 1);
			int numIndices = numQuads * 2 * 3;

			PositionCollection positions = targetMesh.Parent.Positions;
			for( int i = 0; i < numVerts; i++ )
			{
				int idx = positions.Count;
				positions.Add( verts[i].Position );
				targetMesh.Vertices.Add( idx );
			}

			VertexChannel<Vector2> texCoords = targetMesh.Vertices.Channels.Add<Vector2>( VertexChannelNames.TextureCoordinate( 0 ), null );
			VertexChannel<Vector2> litCoords = targetMesh.Vertices.Channels.Add<Vector2>( VertexChannelNames.TextureCoordinate( 1 ), null );
			VertexChannel<Vector3> normals = targetMesh.Vertices.Channels.Add<Vector3>( VertexChannelNames.Normal( 0 ), null );
			VertexChannel<Color> colors = targetMesh.Vertices.Channels.Add<Color>( VertexChannelNames.Color( 0 ), null );

			for( int i = 0; i < numVerts; i++ )
			{
				DrawVert dv = verts[i];

				texCoords[i] = dv.TextureCoord;
				litCoords[i] = dv.LightmapCoord;

				Vector3 norm = dv.Normal;
				normals[i] = new Vector3( norm.X, norm.Y, norm.Z );

				colors[i] = dv.Color;
			}

			int[] indices = new int[4];

			for( int i = 0; i < numQuads; i++ )
			{
				int rowNum = i / (width - 1);

				indices[0] = i + rowNum;
				indices[1] = i + rowNum + 1;
				indices[2] = indices[1] + width;
				indices[3] = indices[0] + width;

				/*
					First we find the best way to split the quad.
			
					In the case of a planar quad this is arbitrary.

					When a quad is non-planar we take the first triangle
					of each of the two possible splits and find the distance
					of the remaining point from the plane of the triangle.

					We choose the split that minimizes this distance
					(thus minimizing the angle of the folded edge).
				*/

				float d02, d13;
				Vector3 e01, e02, e13, c;

				e01 = verts[indices[0]].Position - verts[indices[1]].Position;
				e02 = verts[indices[0]].Position - verts[indices[2]].Position;
				e13 = verts[indices[1]].Position - verts[indices[3]].Position;

				//try splitting along 0-2
				c = Vector3.Cross( e01, e02 );

				if( VectorNormalize( ref c ) > 1e-6 )
					d02 = Vector3.Dot( c, e13 );
				else
					//degenerate or very small triangle, don't care about order
					d02 = 0;

				//try splitting along 1-3
				c = Vector3.Cross( e01, e13 );

				if( VectorNormalize( ref c ) > 1e-6 )
					d13 = Vector3.Dot( c, e02 );
				else
					//degenerate or very small triangle, don't care about order
					d13 = 0;

				//generat the final indices
				if( d02 < d13 )
				{
					//split along 0-2
					targetMesh.Indices.Add( indices[0] );
					targetMesh.Indices.Add( indices[2] );
					targetMesh.Indices.Add( indices[1] );

					targetMesh.Indices.Add( indices[2] );
					targetMesh.Indices.Add( indices[0] );
					targetMesh.Indices.Add( indices[3] );
				}
				else
				{
					//split along 1-3
					targetMesh.Indices.Add( indices[0] );
					targetMesh.Indices.Add( indices[3] );
					targetMesh.Indices.Add( indices[1] );

					targetMesh.Indices.Add( indices[2] );
					targetMesh.Indices.Add( indices[1] );
					targetMesh.Indices.Add( indices[3] );
				}
			}
		}
	}
}